package com.sourcetrip.my;


import com.sourcetrip.my.abs.AbstractList;
import com.sourcetrip.my.modle.LinkedNode;

/**
 * @author: ZhouBert
 * @date: 2020/12/13
 * @description: linkedList 双向链表
 * 设计关键：
 * 1.内部通过双向链表 实现；
 * 2.由于使用了双向链表，查找元素时通过判断 index 靠近 头或者尾，选择开始位置；
 * --
 * 难点：
 * 1.关于 add() 和 remove() 都需要考虑头节点和尾节点的处理
 * --
 * 修复
 * 1.node() 中对于 add() 调用时增加对于  index == size 时的判断；
 */
public class LinkedListV0<E> extends AbstractList<E> {

	/**
	 * 双向链表头节点
	 */
	private LinkedNode<E> head;

	/**
	 * 双向链表尾节点
	 */
	private LinkedNode<E> tail;

	@Override
	public void clear() {
		head = null;
		tail = null;
		size = 0;
	}

	/**
	 * 根据索引获取元素（由于链表并没有真正的索引，只能遍历）
	 *
	 * @param index
	 * @return
	 */
	@Override
	public E get(int index) {
		rangeCheck(index);
		LinkedNode<E> node = node(index);
		return node.ele;
	}

	/**
	 * 设置 index 处的元素
	 *
	 * @param index
	 * @param element
	 * @return
	 */
	@Override
	public E set(int index, E element) {
		rangeCheck(index);
		LinkedNode<E> node = node(index);
		E oldValue = node.ele;
		node.ele = element;
		return oldValue;
	}

	/**
	 * 往 index 处添加 元素
	 * 1.第一个元素时特别处理；
	 * 2.其他情况分别处理 前驱结点 和 后继节点
	 * @param index
	 * @param element
	 */
	@Override
	public void add(int index, E element) {
		rangeCheckForAdd(index);
		LinkedNode<E> node = node(index);
		LinkedNode<E> cur = new LinkedNode<>(element);
		//前驱节点 -- 用局部变量传给下面一个前驱节点，省去了下面处理过程中复杂的判断！！！
		LinkedNode<E> prevNode = node == null ? tail : node.prev;

		//如果没有一个元素 -- 这个处理是有问题的
//		if (node == null) {
//			head = cur;
//			tail = cur;
//			size++;
//			return;
//		}

		//此时没有元素
		if (head == null) {
			head = cur;
			tail = cur;
			size++;
			return;
		}
		//此时添加的是末尾的元素
//		if (node == null) {
//
//		}


		//1.处理前驱节点的 after
		if (prevNode != null) {
			prevNode.after = cur;
			cur.prev = prevNode;
		} else {
			//说明添加到的是头节点的位置
			head = cur;
		}

		//2.处理后继节点的 prev
		if (node != null) {
			cur.after = node;
			node.prev = cur;
		} else {
			//说明添加到的是尾节点的位置
			tail = cur;
		}
		size++;
//		System.out.println(this);
		return;
	}

	/**
	 * 移除 index 处的元素
	 *
	 * @param index
	 * @return
	 */
	@Override
	public E remove(int index) {
		rangeCheck(index);
		LinkedNode<E> node = node(index);

		//1.处理前驱节点的 after
		if (node.prev != null) {
			node.prev.after = node.after;
		} else {
			//说明删除的是 head 节点
			head = node.after;
		}
		//2.处理后继节点的 prev
		if (node.after != null) {
			node.after.prev = node.prev;
		} else {
			tail = node.prev;
		}

		size--;
//		System.out.println(this);
		return node.ele;
	}

	/**
	 * 遍历元素
	 *
	 * @param element
	 * @return
	 */
	@Override
	public int indexOf(E element) {
		LinkedNode<E> cur = this.head;
		if (element == null) {
			for (int i = 0; i < size; i++) {
				if (cur.ele == null) {
					return i;
				}
				cur = cur.after;
			}
		}
		for (int i = 0; i < size; i++) {
			if (element.equals(cur.ele)) {
				return i;
			}
			cur = cur.after;
		}
		return ELEMENT_NOT_FOUND;
	}


	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		LinkedNode<E> cur = this.head;
		for (int i = 0; i < size; i++) {
			if (i != 0) {
				sb.append(", ");
			}
			sb.append(cur.ele);
			cur = cur.after;
		}
		return sb.append("]").toString();
	}


	//region	private methods

	/**
	 * 通过 index 查找 linkedNode
	 *
	 * @param index
	 * @return
	 */
	private LinkedNode node(int index) {
		//1.当添加到 最后的位置时，直接返回 null
		if (index == size) {
			return null;
		}

		LinkedNode<E> cur = head;
		//如果索引值 > 容量的一半
		if (index > (size >> 1)) {
			//从后面开始找
			cur = tail;
			int count = size - index;
			for (int i = 1; i < count; i++) {
				cur = cur.prev;
			}
			return cur;
		}

		//从前面开始找
		for (int i = 0; i < index; i++) {
			cur = cur.after;
		}
		return cur;
	}

	//endregion

}
